On the symmetric travelling salesman problem I: Inequalities

We investigate several classes of inequalities for the symmetric travelling salesman problem with respect to their facet-defining properties for the associated polytope. A new class of inequalities called comb inequalities is derived and their number shown to grow much faster with the number of cities than the exponentially growing number of subtour-elimination constraints. The dimension of the travelling salesman polytope is calculated and several inequalities are shown to define facets of the polytope. In part II (On the travelling salesman problem II: Lifting theorems and facets) we prove that all subtour-elimination and all comb inequalities define facets of the symmetric travelling salesman polytope.     

Computational complexity of LCPs associated with positive definite symmetric matrices

Murty in a recent paper has shown that the computational effort required to solve a linear complementarity problem (LCP), by either of the two well known complementary pivot methods is not bounded above by a polynomial in the size of the problem. In that paper, by constructing a class of LCPs—one of ordern forn 2—he has shown that to solve the problem of ordern, either of the two methods goes through 2 ⁿ pivot steps before termination.However that paper leaves it as an open question to show whether or not the same property holds if the matrix,M, in the LCP is positive definite and symmetric. The class of LCPs in whichM is positive definite and symmetric is of particular interest because of the special structure of the problems, and also because they appear in many practical applications.In this paper, we study the computational growth of each of the two methods to solve the LCP, (q, M), whenM is positive definite and symmetric and obtain similar results.This research is partially supported by Air Force Office of Scientific Research, Air Force Number AFOSR-78-3646. The United States Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright notation thereon.     

Many-to-many location-routing with inter-hub transport and multi-commodity pickup-and-delivery

In this paper, we consider a variant of the many-to-many location-routing problem, where hub facilities have to be located and customers with either pickup or delivery demands have to be combined in vehicle routes. In addition, several commodities and inter-hub transport processes are taken into account. A practical application of the problem can be found in the timber-trade industry, where companies provide their services using hub-and-spoke networks. We present a mixed-integer linear model for the problem and use CPLEX 12.4 to solve small-scale instances. Furthermore, a multi-start procedure based on a fix-and-optimize scheme and a genetic algorithm are introduced that efficiently construct promising solutions for medium- and large-scale instances. A computational performance analysis shows that the presented methods are suitable for practical application.     

How do we know who to include in collaborative research? Toward a method for the identification of experts

Collaborative research, defined as research involving actors participating in the problem situation under study, has an important role in operational research, strategic management and systems thinking. In a recent study, we found that a strong organizational focus incorporated into many soft operational research (OR) approaches is inadequate for studying societal problem situations, which are fragmented and have no clear boundary. Specifically, we failed to find a process of identifying individuals that is capable of representing the perspectives of actors and sufficient for research into societal problem situations. We found no clear terminology accounting for ontological differences between actors, individuals representing them and conceptual representations of acting entities. In response to this gap in the literature, we propose terminology that differentiates among actors (individuals or collective entities in the real world), experts (individuals capable of representing the perspective of an actor) and agents (ideal-typical representations of actors). Based on this terminology, we propose an iterative method to guide the assembly of an expert group to undertake collaborative research into societal problem situations. To demonstrate the application of our method, we present selected insights from our study in an electronic supplement.     

A bi-objective mathematical model toward dynamic cell formation considering labor utilization

This paper addresses dynamic cell formation problem (DCFP) via a new bi-objective mathematical formulation. Although literature body of DCFP includes a vast number of research instances, human-related issues are mostly neglected as an important aspect of DCFP in the corresponding literature. In this paper, the first objective function seeks to minimize relevant costs of the problem including machine procurement and relocation costs, machine variable cost, inter-cell movement and intra-cell movement costs, overtime cost and labor shifting cost between cells, while labor utilization of the modeled DCFP is maximized through the second objective function. Due to NP-hardness of DCFP, an ant colony optimization (ACO) meta-heuristic is developed for the first time in the literature to tackle the problem. Also, authors enhance diversification of the developed algorithm is enhanced by hybridization of the proposed ACO algorithm with a genetic one. Finally, some numerical samples are generated randomly to validate the proposed model by which strengths of the developed algorithm is shown.     

The Capacitated Team Orienteering Problem: A Bi-level Filter-and-Fan method

This paper focuses on vehicle routing problems with profits and addresses the so-called Capacitated Team Orienteering Problem. Given a set of customers with a priori known profits and demands, the objective is to find the subset of customers, for which the collected profit is maximized, and to determine the visiting sequence and assignment to vehicle routes assuming capacity and route duration restrictions. The proposed method adopts a hierarchical bi-level search framework that takes advantage of different search landscapes. At the upper level, the solution space is explored on the basis of the collected profit, using a Filter-and-Fan method and a combination of profit oriented neighborhoods, while at the lower level the routing of customers is optimized in terms of traveling distance via a Variable Neighborhood Descent method. Computational experiments on benchmark data sets illustrate the efficiency and effectiveness of the proposed approach. Compared to existing results, new upper bounds are produced with competitive computational times.     

Time optimality and the maximum principle in infinite dimension

We present three counterexamples related to the maximum principle for the time optimal problem. The system is linear, infinite dimensional, with point target and “full” control     

Operations research in the space industry

Operations research techniques have been used in the space industry since its infancy, and various competing methods and codes, with widely varying characteristics, have been used over time. This survey is intended to give an overview of current application cases of different operations research techniques and methodologies in the domain of space engineering and space science.     

Simple matching vs linear assignment in scheduling models with positional effects: A critical review

This paper addresses scheduling models in which a contribution of an individual job to the objective function is represented by the product of its processing time and a certain positional weight. We review most of the known results in the area and demonstrate that a linear assignment algorithm as part of previously known solution procedures can be replaced by a faster matching algorithm that minimizes a linear form over permutations. Our approach reduces the running time of the resulting algorithms by up to two orders, and carries over to a wider range of models, with more general positional effects. Besides, the same approach works for the models with no prior history of study, e.g., parallel machine scheduling with deterioration and maintenance to minimize total flow time.     

An investigation of preservice teachers’ use of guess and check in solving a semi open-ended mathematics problem

Open-ended problems have been regarded as powerful tools for teaching mathematics. This study examined the problem solving of eight mathematics/science middle-school teachers. A semi-structured interview was conducted with (PTs) after completing an open-ended triangle task with four unique solutions. Of particular emphasis was how the PTs used a specific heuristic strategy. The results showed that the primary strategy PTs employed in attempting to solve the triangle problem task was guess and check; however, from the PTs’ reflections, we found there existed misapplications of guess and check as a systematic problem-solving strategy. In order to prepare prospective teachers to effectively teach, teacher educators should pay more attention to the mathematical proficiency of PTs, particularly their abilities to systematically and efficiently use guess and check while solving problems and explain their solutions and reasoning to middle-school students.